package airthmetic.exercise.dp;

// 经典dp的0-1背包问题
//1.1、问题描述
//      给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]。
//      现在让你用这个背包装物品，每种物品可以选0个或1个，问最多能装的价值是多少？
public class BackPack4 {


    /**
     *
     * @param wt 每个物品的重量 即wt[i]是第i个物品的重量
     * @param v  每个物品的价值 即v[i]是第i个物品的价值
     * @param N  物品个数
     * @param W  背包重量
     * @return 最多能装多少价值
     */
    public static int dp(int[] wt, int[] v, int N, int W) {
        /**
         * 因为问题具备重叠子问题和无后效性及最优子结构。动态规划！
         *  重叠子问题；W重量的背包最多能装多少价值的物品
         *  无后效性：W重量的背包最多能装多少价值的物品不会被后续问题求解改变
         *  最优子结构：问题之间独立，并且W重量的背包最多能装多少价值的物品可以被后续问题使用
         *
         * 动态规划思考问题。
         *  什么是原问题？ 什么是子问题？
         *      原问题：W重量的背包前i个物品最多能装多少价值？
         *      子问题：W-1重量的背包钱i-1个物品最多能装多少价值？
         *
         *      1.确定状态参数和选择
         *          状态参数：状态参数是在原问题于子问题之间不断变化的值
         *              W：重量
         *              i：前i个物品
         *
         *          选择/决策: 做选择使状态参数不断变化并趋近于原问题的解
         *              不断选择不同的W和i
         *
         *      2.定义dp table的含义
         *          int[][] dp = new int[N+1][W+1];
         *          dp[i][w] = w重量 前i个个物品能装的最大价值
         *
         *      3.初始化 dp table
         *          dp[i][0] 当背包容量为0时，不管前几个物品都无法装出价值
         *          dp[0][w] 当物品为0时，不管背包容量是多少都无法装出价值
         *
         *      4推导状态转移公式
         *          当商品重量大于背包容量时，从w容量 i-1物品重量转移过来
         *          当商品重量小于等于背包容量时，从w容量-wt[i-1] 前i个物品 v[i-1] -
         *          for(int i=1; i<=N; i++){
         *              for(int w=1; w<=W; w++){
         *                  if(wt[i - 1] > w){
         *                      dp[i][w] = dp[i-1][w];
         *                  }else{
         *                      dp[i][w] = Math.max(dp[i][w],dp[i-1][w-wt[i-1]] + v[i-1]);
         *                  }
         *              }
         *          }
         *
         *
         */
        int[][] dp = new int[N+1][W+1];
        for(int i=1; i<=N; i++){
            for(int w=1; w<=W; w++){
                if(wt[i - 1] > w){
                    dp[i][w] = dp[i-1][w];
                }else{
                    dp[i][w] = Math.max(dp[i-1][w],dp[i-1][w-wt[i-1]] + v[i-1]);
                }
            }
        }


        return dp[N][W];
    }

    public static void main(String[] args) {
        int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
        int[] wt = {3, 2, 1}; // 物品的重量
        int[] v = {5, 2, 3}; // 物品的价值
        System.out.println(new BackPack().dp(wt,v,N,W));
    }
}

